package com.cfwx.datastructure.sort;

/**
 * 直接选择排序
 * 直接选择排序的基本思想:
 * n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
 * ①初始状态：无序区为R[1..n]，有序区为空。
 * ②第1趟排序
 * 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
 *　......
 * ③第i趟排序
 * 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
 * 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
 * 
 */
public class SelectSort {

	public static void selectSort(int[]R ){
		int n = R.length-1;
		int i,j,k;
		for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)
			k=i;
			for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]
				if(R[j]<R[k]) 
					k=j; //k记下目前找到的最小关键字所在的位置
			if(k!=i){ //交换R[i]和R[k]
				R[0]=R[i];//R[0]作暂存单元
				R[i]=R[k];
				R[k]=R[0]; 
			} 
		} 
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//数组下标是从0开始，将第一个元素置为0即num[0]=0，使待排序序列从下表1开始
		int num[] = new int[] {0, 2221, 5, 40, 32, 2};
		selectSort(num);
		for (int x = 0; x < num.length-1; x++) {
			System.out.print(num[x+1] + " ");
		}
		
	}

}
/**
 * 算法分析
（1）关键字比较次数
    　无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：
     (n-1+1)(n-1)/2=n(n-1)/2=0(n2)

（2）记录的移动次数
    　当初始文件为正序时，移动次数为0
    　文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
    　直接选择排序的平均时间复杂度为O(n2)。

（3）直接选择排序是一个就地排序

（4）稳定性分析
    　直接选择排序是不稳定的
    
 */
